package leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wangmaolin1
 * @date 2022/1/3 下午6:28
 */
public class _501二叉搜索树中的众数 {

    List<Integer> result = new ArrayList<>();
    int maxCount = 0;
    int base = 0;
    int count = 0;

    public int[] findMode(TreeNode root) {

        midOrder(root);
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }

    private void midOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            midOrder(root.left);
        }
        update(root.val);
        if (root.right != null) {
            midOrder(root.right);
        }
    }

    private void update(int num) {
        if (base == num) {
            count++;
        } else {
            base = num;
            count = 1;
        }
        if (count == maxCount) {
            result.add(num);
        }
        if (count > maxCount) {
            maxCount=count;
            result.clear();
            result.add(num);
        }
    }

}
